package com.zhanghp.class022;

import java.io.*;

/**
 * 小和问题
 * 测试链接 : https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
 * 请同学们务必参考如下代码中关于输入、输出的处理
 * 这是输入输出处理效率很高的写法
 * 提交以下的code，提交时请把类名改成"Main"，可以直接通过
 *
 * @author zhanghp
 * @since 2024/3/6 13:58
 */
public class Code01_SmallSum {

    public static int max = 100001;

    public static int[] arr = new int[max];

    public static int[] help = new int[max];

    public static int n;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            out.println(smallSum(0, n - 1));
        }
        out.flush();
        br.close();
        out.close();
    }

    public static long smallSum(int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        // 左部分小和
        long leftSmallSum = smallSum(l, mid);
        // 右部分小和
        long rightSmallSum = smallSum(mid + 1, r);
        // 跨越左右小和
        long mergeSmallSum = merge(l, mid, r);
        // 相加
        return leftSmallSum + rightSmallSum + mergeSmallSum;
    }

    public static long merge(int l, int mid, int r) {
        // 1. 求和
        // long !!!!!!!越界int，会不通过！！！！！！
        long ans = 0;
        for (int a = l, i = mid + 1, sum = 0; i <= r; i++) {
            while (a <= mid && arr[i] >= arr[a]) {
                sum += arr[a++];
            }
            ans += sum;
        }
        // 2. 排序
        int a = l, b = mid + 1, index = l;
        while (a <= mid && b <= r) {
            help[index++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= mid) {
            help[index++] = arr[a++];
        }
        while (b <= r) {
            help[index++] = arr[b++];
        }
        for (index = l; index <= r; index++) {
            arr[index] = help[index];
        }
        return ans;
    }
}
